# 给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
#  你可以返回满足此条件的任何数组作为答案。
#
#  示例：
#  输入：[3,1,2,4]
# 输出：[2,4,3,1]
# 输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
from typing import List


class Solution:
    def sortArrayByParity2(self, nums: List[int]) -> List[int]:
        """
        双指针
        维护两个指针 i,j。(i从前向后, j从后向前)
        遍历数组 如果 nums[i]为奇数，则不断地向前移动j，直到遇见下一个偶数。 此时，可以直接将 nums[i]与 nums[j]交换。
        :param nums:
        :return:
        """
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] % 2 == 1:
                while i < j and nums[j] % 2 == 1:
                    j -= 1

                nums[i], nums[j] = nums[j], nums[i]

            i += 1
        return nums

    def sortArrayByParity1(self, nums: List[int]) -> List[int]:
        res = nums.copy()
        even, odd = 0, len(nums) - 1
        for num in nums:
            if num % 2 == 0:
                res[even] = num
                even += 1
            else:
                res[odd] = num
                odd -= 1
        return res

    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        return self.sortArrayByParity2(nums)

if __name__ == "__main__":
    nums = [3, 1, 2, 4]
    r = Solution().sortArrayByParity(nums)
    print(r)
